package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/15 20:05
 **/
public class BinarySearch1 {

    public static void main(String[] args) {
        int[] arr = {0,3,4,7,9,10,200};
        System.out.println(binarySearch_2(arr, 3));
    }

    /**
     * 要求我们在一个有序数组里查找目标元素的下标，目标元素不存在，返回-1
     *
     * 这里要注意，大前提是有序数组，二分查找只能针对有序数组。
     * @param arr
     * @param target
     */
    private static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            // 这里如果left, right过大，可能会出现整型int溢出问题，所以可以替换下面的写法
            //int mid = (left + right) / 2;
            int mid = left + (right - left) / 2;
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                return 0;
            }
        }
        return -1;
    }

    /**
     * 二分查找的另一种思路
     * 将不存在的区间排除，缩小查找的范围
     * @param arr
     * @param target
     * @return
     */
    private static int binarySearch_2(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        // 这里循环不加等号，因为如果left == right 也就是区间还剩下最后一个元素，只要这个元素与目标相同即可，否则返回-1
        while (left < right) {
            // 这里计算 中间必须要向上取整也就是+1，否则会死循环
            // 原因是，如果这里left=1，而right=2，那么mid=1，此时如果target < arr[mid]，那么mid = 1，left = 1，right = 2，那么此时就是死循环
            // 也就是如果区间元素只剩下两个元素，而且其中一个元素，还是大于目标元素的话，就会死循环
            int mid = left + (right - left + 1) / 2;
            if (target < arr[mid]) {
                // 查找区间 [left, mid - 1]
                right = mid - 1;
            } else {
                // 查找区间 [mid, right]
                // 这里要注意边界，需要把mid包含进去
                left = mid;
            }
        }
        if (arr[left] == target) {
            return left;
        }
        return -1;
    }
}
